package leetcode;

import java.util.Deque;
import java.util.LinkedList;

//柱状问题的子问题，将矩阵中的每一行看成一个数组，然后求最大的矩阵面积和
public class MaximalRectangle {

	public static void main(String[] args) {
		MaximalRectangle object = new MaximalRectangle();
		int[] heights = {3, 1, 3, 2, 1};
		object.largestSquareArea(heights);
	}
	
	//You can maintain a row length of Integer array matrix recorded its height of '1's, 
	//and scan and update row by row to find out the largest rectangle of each row.
	
    public int maximalRectangle(char[][] matrix) {
    	if(matrix == null || matrix.length <= 0 || matrix[0].length <= 0){
    		return 0;
    	}
    	int rows = matrix.length; 
    	int columns = matrix[0].length; 
    	//用以存储整数，每一列的值表示从 0 - i行中j列中 连续1的个数
    	//比如 1 0 1 0 0  
    	//    1 0 1 1 1
    	//    1 1 1 1 1 
    	//height[i][j]的结果是
    	//    1 0 1 0 0
    	//    2 0 2 1 1
    	//    3 1 3 2 2  //最大直方图面积为6（3个高度为2的柱子3 * 2）
    	//然后求每一行的最大面积，得出最大值即可
    	int[][] heights = new int[rows][columns];
    	int max = 0 , curMax = 0;
    	for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				if(matrix[i][j] == '1'){
	                heights[i][j] = (i == 0) ? 1 : heights[i - 1][j] + 1;
	            }else {
					heights[i][j] = 0;  //为‘0’ 的时候就为整数0
				}
			}
			curMax = largestRectangleArea(heights[i]);
			max = Math.max(curMax, max);
		}
    	return max;
    }

    //用来求最大的直方图面积
	public int largestRectangleArea(int[] heights) {
		Deque<Integer> stack = new LinkedList<Integer>();
		int max = 0, curMax = 0;
		for (int i = 0; i <= heights.length; i++) {
			while (!stack.isEmpty()
					&& (i == heights.length || heights[stack.peek()] >= heights[i])) {
				curMax = (heights[stack.pop()])
						* (stack.isEmpty() ? i : i - stack.peek() - 1);
				if (curMax > max)
					max = curMax;
			}
			stack.push(i);
		}
		return max;
	}
	
	
    //用来求最大的正方形面积
	public int largestSquareArea(int[] heights) {
		Deque<Integer> stack = new LinkedList<Integer>();
		int max = 0, curMax = 0;
		for (int i = 0; i <= heights.length; i++) {
			while (!stack.isEmpty()
					&& (i == heights.length || heights[stack.peek()] >= heights[i])) {
				int length = 0;
				int high = heights[stack.pop()];
				length = stack.isEmpty() ? i : i - stack.peek() - 1;
				System.out.println("index: " + i);
				System.out.println("底边长: " + length + " 高:" + high);
				curMax = (int) Math.pow(Math.min(high, length), 2);
				System.out.println("area: " + curMax);
				if (curMax > max)
					max = curMax;
			}
			stack.push(i);
		}
		return max;
	}
}
